1. Field of the Invention
The present invention relates to image authentication, and more particularly relates to methods and apparatus for image authentication which distinguish unauthorized content-altering image alterations from content preserving manipulations, such as image compression.
2. Description of Related Art
With the recent growth in accessability of computers and digital cameras, the importance of digital images is constantly increasing. Digital images offer advantages over traditional photographic processes in ease of manipulation, storage and processing. However, the ease in which digital images can be altered significantly reduces the reliability which was once inherent in a photographic image.
To enhance the reliability of digital images, image authentication techniques have been pursued to detect malicious manipulation of an image. Previously, two techniques have been investigated: 1) generating a digital signature of the image at the point of origin, i.e., at the digital camera; and 2) embedding a secret code, or xe2x80x9cwatermark,xe2x80x9d related to the content of the image within the image.
The first method employs an encrypted digital signature which is generated by the image capturing device. Generally, the digital signature is based on a public key encryption method. In this type of method, a private key, known only to the capturing device, is used to encrypt a hashed version of an image to form the xe2x80x9csignaturexe2x80x9d of the image which travels with the image. A public key is used to decrypt the signature. The public key is also used to hash the image and compare the codes of the current image to the original signature. If the codes match, the present image is considered authentic.
In the second method, a checksum value is generated corresponding to the bit values of the pixels forming the image. The checksum value is considered a fragile xe2x80x9cwatermarkxe2x80x9d for the image, as any alteration of the image will alter the checksum value and destroy the watermark. To authenticate an image, the current checksum value of the image is compared against the value of the watermark to verify that the values are equal.
Both of the above image authentication methods are limited in that any change in the image will result in a verification failure. However, certain image manipulations do not significantly alter the meaning of the image content and are considered desirable. For example, digital images are generally compressed prior to storage and data transmission in order to optimize the use of computer storage and data transmission resources. However, a very common image compression standard, JPEG (Joint Photographic Experts Group), results in a xe2x80x9clossyxe2x80x9d compression of image data which irrevocably alters certain pixels in the image. Because JPEG compression alters the content of the image, the above described authentication methods cannot successfully verify an image after such lossy compression is applied.
FIGS. 1A and 1B illustrate systems known in the art for performing JPEG compression and decompression of a digital image, respectively. Referring to FIG. 1A, the source image 100, X, is grouped into xcfx81 nonoverlapping 8xc3x978 blocks, O FPIXELS i.e., X=∪p=1xcfx81Xp. Each block is sent sequentially to a Discrete Cosine Transform (DCT) processor 102 to extract DCT coefficients for each block. Instead of representing each block, Xp, as a 8xc3x978 matrix, each block can be represented as a 64xc3x971 vector following the xe2x80x9czig-zagxe2x80x9d order of the original matrix. Therefore, the DCT coefficients Fp, of the vector, Xp, can be considered as a linear transformation of Xp with a 64xc3x9764 transformation matrix D, s.t.,
Fp=DXp.xe2x80x83xe2x80x83(1)
Each of the 64 DCT coefficients is applied to a quantizer 104 where the DCT coefficients are quantized with a 64-element quantization table Q 106. In JPEG compression, this table is used on all blocks of an image. (For color images, there could be three quantization tables for CrCb domains, respectively.) Quantization is defined as the division of each DCT coefficient by its corresponding quantizer step size, followed by rounding to the nearest integer:                                                         f              ~                        p                    ⁡                      (            v            )                          ≡                  Integer          ⁢                      xe2x80x83                    ⁢          Round          ⁢                      xe2x80x83                    ⁢                      (                                                            F                  p                                ⁡                                  (                  v                  )                                                            Q                ⁡                                  (                  v                  )                                                      )                                              (        2        )            
where xcexd=1 . . . 64. In eq.(2), {tilde over (f)}p is the output of the quantizer. For the convenience of later discussion, we can define {tilde over (F)}p, a quantized approximation of Fp, as
{tilde over (F)}p(xcexd)xe2x89xa1{tilde over (F)}p(xcexd)xc2x7Q(xcexd).xe2x80x83xe2x80x83(3)
After quantization, the inter-block differences of DC coefficients are encoded by an entropy encoder 108. The AC terms are ordered following the xe2x80x9czig-zagxe2x80x9d order. Both DC and AC coefficients are then entropy encoded. The final JPEG file, {tilde over (B)} includes the Huffman table 110, the quantization table 106, the encoded data and some other information.
FIG. 1B illustrate a decoder suitable for decompressing an image subjected to JPEG compression. First, the decoder extracts and reconstructs the Huffman table 110 and quantization table 106 from the compressed image. Then the bitstream is sent to an entropy decoder 112 and a dequantizer 114 to substantially reconstruct the DCT coefficients of the original image. The output of dequantizer, {tilde over (F)}p, is the same as that defined above in equation(3). An Inverse DCT (IDCT) processor 116 is then used to convert {tilde over (F)}p to the spatial-domain image block {tilde over (X)}p.
{tilde over (X)}p=Dxe2x88x921{tilde over (F)}p.xe2x80x83xe2x80x83(4)
All blocks are then tiled to form a decoded image frame.
Theoretically, the results of the IDCT process will be real numbers. However, the brightness of an image is usually represented by an 8-bit integer from 0 to 255. Therefore, a rounding process which maps those real numbers to integers may be necessary. This process is performed after the IDCT processor 116 by processing block 118.
In addition to image compression, it is also desirable to allow certain other manipulations to an image while still verifying the remaining content as authentic. In some cases image cropping, image translation, image masking, global intensity alteration etc. may be allowable. However, as with lossy compression, present image authentication techniques cannot verify an image once such allowable image manipulations are performed.
The above-described prior art techniques fail to satisfy the growing need for robust image authentication which can distinguish between allowable image manipulations and malicious, content altering manipulations which are impermissible.
An object of the present invention is to provide robust image authentication methods and apparatus which distinguish malicious content based attacks of an image from allowable transformations of an image.
A further object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to format transformation, lossless compression as well as acceptable forms of lossy compression.
Another object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to user specified content manipulations, such as cropping, shifting and image intensity adjustment.
Yet another object of the present invention is to provide an image authenticator which accepts and authenticates images subjected to JPEG image compression.
In accordance with a first embodiment of the present invention a system for authentication of a digital image includes a signature generator and an authentication processor. The signature generator includes an image analyzer which receives an original digital image, parses the image into block pair and generates invariant features of the image based on a relationship between corresponding pixels in the block pairs. Preferably, the signature generator also includes an encryption processor for encoding the invariant features generated by the image analyzer in accordance with encryption key data, thereby providing an encrypted signature for the image. The authentication processor receives a digital image to be authenticated as well as the signature for the original image. When the signature is encrypted, the authentication processor includes a decryption processor for decrypting the signature in accordance with decryption key data to extract the invariant features of the original image. The authentication processor further includes means for extracting coefficients of the image to be authenticated and an authentication comparator. The authentication comparator receives the coefficients of the image to be authenticated, extracts invariant features of the image to be authenticated based on a relationship between corresponding coefficients and compares the invariant features from the original image to those of the image to be authenticated to provide a signal indicative of an authentication failure if the corresponding features are not substantially equal.
Preferably, the relationship between corresponding pixels used to form the invariant features is the polarity of the difference of discrete cosine transform coefficients of corresponding coefficient locations in pairs of non-overlapping blocks of the image. The relationship preferably further includes the relative magnitude of the difference of discrete cosine transform coefficients of corresponding coefficient locations in the pairs of non-overlapping blocks of the image.
Preferably, the authentication system of the present invention can accept digital image data in the form of a raw image or a JPEG compressed bit stream. When the digital image to be authenticated is in the form of a raw image, the means for extracting invariant features includes a discrete cosine transform processor which receives the raw image and provides discrete cosine transform coefficients representing the raw image to the authentication comparator. When the digital image to be authenticated is in the form of a JPEG compressed image bit stream, the means for extracting invariant features includes a JPEG decoder which provides discrete cosine transform coefficients representing the raw image to the authentication comparator.
In accordance with another form of the present invention, a signature generator for providing a robust digital signature for a digital image includes an image analyzer which receives an original digital image, parses the image into at least one image block pair and generates substantially invariant features of the image. The invariant features correspond to a relationship between corresponding coefficient values in block pairs which remains unaltered during allowable image manipulations.
The relationship between corresponding coefficients includes the polarity of the difference of discrete cosine transform coefficients of corresponding coefficients locations of image block pair. Preferably, the relationship further includes the relative magnitude of the difference of discrete cosine transform coefficients of corresponding locations of the image block pairs.
In accordance with another form of the present invention, a digital image authenticator is formed for receiving data representing a digital image to be authenticated and a digital signature for the original image. The authenticator includes means for generating coefficients from the data representing the image to be authenticated, means for extracting invariant features for the original image from the digital signature and an authentication comparator. The authentication comparator receives the coefficients from the generating means and generates invariant features for the image to be authenticated from the coefficients. The authentication comparator then compares corresponding invariant features of the present image to those invariant features from the original image and provides a signal indicative of an authentication failure if the corresponding invariant features do not exhibit an expected relationship.
The expected relationship is at least partially defined by the polarity of the difference of discrete cosine transform coefficients of corresponding locations in non-overlapping block pairs of the image. Preferably, the expected relationship is further defined by the magnitude of the difference of discrete cosine transform coefficients of corresponding locations in non-overlapping block pairs of the image.
In accordance with a method of the present invention, an invariant feature for a digital image is formed by the following steps: partitioning the image into a plurality of image blocks; assigning image block pairs from the plurality of image blocks; extracting DCT coefficients in the image block pairs and determining an invariant relationship between corresponding coefficients DCT of the image block pairs.
In this method, the relationship is at least partially defined by the polarity of the difference of corresponding coefficients. Preferably, the relationship is further defined by the magnitude of the difference of the corresponding coefficients.